#
# @lc app=leetcode.cn id=1365 lang=python3
#
# [1365] 有多少小于当前数字的数字
#
from typing import List


# @lc code=start
class Solution:
    def smallerNumbersThanCurrent1(self, nums: List[int]) -> List[int]:
        a = [0] * 101
        for i in nums:
            a[i] += 1
        for i in range(1, 101):
            a[i] += a[i - 1]

        for i, v in enumerate(nums):
            if v == 0:
                nums[i] = 0
            else:
                nums[i] = a[v - 1]
        return nums

    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        s = sorted([(v, i) for i, v in enumerate(nums)], key=lambda x: x[0])
        c = 0
        for i, v in enumerate(s):
            if i > 0 and v[0] > s[i-1][0]:
                c = i
            nums[v[1]] = c
        return nums


if __name__ == "__main__":
    s = Solution()
    print(s.smallerNumbersThanCurrent([8, 1, 2, 2, 3]), [4, 0, 1, 1, 3])
    print(s.smallerNumbersThanCurrent([6, 5, 4, 8]), [2, 1, 0, 3])
    print(s.smallerNumbersThanCurrent([7, 7, 7, 7]), [0, 0, 0, 0])
# @lc code=end
